{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Word in Dictionary through Deleting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLongestWord"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通过删除字母匹配到字典里最长单词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个字符串数组 <code>dictionary</code> ，找出并返回&nbsp;<code>dictionary</code> 中最长的字符串，该字符串可以通过删除 <code>s</code> 中的某些字符得到。</p>\n",
    "\n",
    "<p>如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abpcplea\", dictionary = [\"ale\",\"apple\",\"monkey\",\"plea\"]\n",
    "<strong>输出：</strong>\"apple\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abpcplea\", dictionary = [\"a\",\"b\",\"c\"]\n",
    "<strong>输出：</strong>\"a\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= dictionary.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= dictionary[i].length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 和 <code>dictionary[i]</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-word-in-dictionary-through-deleting](https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-word-in-dictionary-through-deleting](https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abpcplea\"\\n[\"ale\",\"apple\",\"monkey\",\"plea\"]', '\"abpcplea\"\\n[\"a\",\"b\",\"c\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        # a:0,7 \n",
    "        # l:5\n",
    "        # e:6\n",
    "        # p:2,4 \n",
    "        # cur = -1\n",
    "        arr = [[] for _ in range(26)]\n",
    "        A = ord('a')\n",
    "        for i in range(len(s)): arr[ord(s[i]) - A].append(i)\n",
    "        ans = \"\"\n",
    "        for w in dictionary:\n",
    "            cur = -1\n",
    "            flag = True\n",
    "            for c in w:\n",
    "                idx = bisect.bisect_right(arr[ord(c) - A], cur)\n",
    "                if idx == len(arr[ord(c) - A]):\n",
    "                    flag = False\n",
    "                    break\n",
    "                cur = arr[ord(c) - A][idx]\n",
    "            if flag:\n",
    "                if len(w) > len(ans): ans = w\n",
    "                elif len(w) == len(ans): ans = min(ans, w)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        n = len(dictionary)\n",
    "        cont = [0]*n\n",
    "        out = ''\n",
    "        for w in s:\n",
    "            for i in range(n):\n",
    "                if cont[i] < len(dictionary[i]) and w == dictionary[i][cont[i]]:\n",
    "                    cont[i] += 1\n",
    "                    if cont[i] == len(dictionary[i]):\n",
    "                        if cont[i] > len(out) or (cont[i]==len(out) and dictionary[i] < out):\n",
    "                            out = dictionary[i]\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        \n",
    "        def match(s: str, d: str) -> bool:\n",
    "            l1, l2 = len(s), len(d)\n",
    "            i, j = 0, 0\n",
    "            while True:\n",
    "                if i == l1 or j == l2:\n",
    "                    break\n",
    "                if s[i] == d[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            return j == l2\n",
    "        \n",
    "        ans = ''\n",
    "        for d in dictionary:\n",
    "            if match(s, d) and (len(d) > len(ans) or len(d) == len(ans) and d < ans):\n",
    "                ans = d\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res=\"\"\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        for t in dictionary:\n",
    "            i=0\n",
    "            j=0\n",
    "            ##建立两个索引\n",
    "            while i<len(s) and j<len(t) :\n",
    "                 if t[j]== s[i]:\n",
    "                     j+=1\n",
    "                 i+=1\n",
    "            if(j==len(t)):\n",
    "                if(len(t)>len(self.res) or(len(self.res)==len(t) and t<self.res)):\n",
    "                    self.res=t\n",
    "        return self.res;\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        dp = defaultdict(lambda: defaultdict(lambda: n))\n",
    "        # dp = [[0] * 26 for _ in range(n)]\n",
    "        # dp.append([n] * 26)\n",
    "\n",
    "        for i in reversed(range(n)):\n",
    "            for j in range(26):\n",
    "                if ord(s[i]) == j + 97:\n",
    "                    dp[i][j] = i\n",
    "                else:\n",
    "                    dp[i][j] = dp[i + 1][j]\n",
    "\n",
    "        def edit(s, t):\n",
    "            i = j = 0\n",
    "            for j in range(len(t)):\n",
    "                if dp[i][ord(t[j]) - 97] == n:\n",
    "                    return False\n",
    "                i = dp[i][ord(t[j]) - 97] + 1\n",
    "\n",
    "            return True\n",
    "\n",
    "        ans = ''\n",
    "        for t in dictionary:\n",
    "            if edit(s, t):\n",
    "                ans = min(ans, t, key=lambda x: (-len(x), x))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        m = {i: {} for i in range(-1, len(s))}\n",
    "        for i in range(-1, len(s)):\n",
    "            for c in \"abcdefghijklmnopqrstuvwxyz\":\n",
    "                try:\n",
    "                    m[i][c] = s.index(c, i + 1)\n",
    "                except:\n",
    "                    m[i][c] = None\n",
    "        for word in sorted(dictionary, key=lambda w: (-len(w), w)):\n",
    "            i = -1\n",
    "            is_ans = True\n",
    "            for c in word:\n",
    "                i = m[i][c]\n",
    "                if i is None:\n",
    "                    is_ans = False\n",
    "                    break\n",
    "            if is_ans:\n",
    "                return word\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        def check(string):\n",
    "            start, c_start = 0, 0\n",
    "            while start < len(string) and c_start < len(s):\n",
    "                if s[c_start] == string[start]:\n",
    "                    start += 1\n",
    "                    c_start += 1\n",
    "                else:\n",
    "                    c_start += 1\n",
    "            return start == len(string)\n",
    "\n",
    "        dictionary.sort()\n",
    "        res = ''\n",
    "        length = 0\n",
    "        for string in dictionary:\n",
    "            if check(string):\n",
    "                if len(string) > length:\n",
    "                    res = string\n",
    "                    length = len(string)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        m = {i: {} for i in range(-1, len(s))}\n",
    "        for i in range(-1, len(s)):\n",
    "            for c in \"abcdefghijklmnopqrstuvwxyz\":\n",
    "                try:\n",
    "                    m[i][c] = s.index(c, i + 1)\n",
    "                except:\n",
    "                    m[i][c] = None\n",
    "        for word in sorted(dictionary, key=lambda w: (-len(w), w)):\n",
    "            i = -1\n",
    "            is_ans = True\n",
    "            for c in word:\n",
    "                i = m[i][c]\n",
    "                if i is None:\n",
    "                    is_ans = False\n",
    "                    break\n",
    "            if is_ans:\n",
    "                return word\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        def is_sub(x):\n",
    "            if len(x) > len(s):\n",
    "                return False\n",
    "            n = len(x)\n",
    "            j = 0\n",
    "            for i in range(n):\n",
    "                while j < len(s) and x[i] != s[j]:\n",
    "                    j += 1\n",
    "                if j == len(s):\n",
    "                    return False\n",
    "                j += 1\n",
    "            return True\n",
    "\n",
    "        dictionary.sort()\n",
    "        ans = ''\n",
    "        for s1 in dictionary:\n",
    "            if is_sub(s1) and len(s1) > len(ans):\n",
    "                ans = s1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "\n",
    "        def isContain(s:str, t:str) -> bool:\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while j < len(s):\n",
    "                if s[j] == t[i]:\n",
    "                    i += 1\n",
    "                    if i >= len(t):\n",
    "                        return True\n",
    "                j += 1\n",
    "            return False\n",
    "\n",
    "        temp = [\"\"]\n",
    "        for t in dictionary:\n",
    "            if isContain(s,t):\n",
    "                temp.append(t)\n",
    "\n",
    "        temp.sort(key=lambda s:(-len(s) , s))\n",
    "        return temp[0]        \n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ret = ''\n",
    "        for word in dictionary:\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(s) and j < len(word):\n",
    "                if s[i] == word[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else: i += 1\n",
    "            if j == len(word):\n",
    "                if len(word) > len(ret): ret = word\n",
    "                elif len(word) == len(ret): ret = min(ret, word)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ret = []\n",
    "        maxLen = 0\n",
    "        n = len(s)\n",
    "        for d in dictionary:\n",
    "            idx1, idx2, k = 0, 0, len(d)\n",
    "            while idx1 < n and idx2 < k:\n",
    "                if s[idx1] == d[idx2]:\n",
    "                    idx2 += 1\n",
    "                idx1 += 1\n",
    "            # print(idx1, idx2, d, s, k, n)\n",
    "            if idx2 == k:\n",
    "                if k > maxLen:\n",
    "                    maxLen = k\n",
    "                    ret = [d]\n",
    "                elif k == maxLen:\n",
    "                    ret.append(d)\n",
    "        ret = sorted(ret)\n",
    "        return ret[0] if ret else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ans = \"\"\n",
    "        for t in dictionary:\n",
    "            i, j = 0, 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(ans) or len(t) == len(ans) and t < ans:\n",
    "                    ans = t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for one in dictionary:\n",
    "            i=j=0\n",
    "            while i<len(one) and j <len(s):\n",
    "                if one[i]==s[j]:\n",
    "                    i+= 1\n",
    "                j += 1\n",
    "            if i==len(one):\n",
    "                if len(one)>len(res) or (len(res)==len(one) and one<res):\n",
    "                    res = one\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key = lambda x:(-len(x),x))\n",
    "        for d in dictionary:\n",
    "            i,j = 0,0\n",
    "            if len(d) > len(s):\n",
    "                continue\n",
    "            while i<len(d) and j<len(s):\n",
    "                if d[i] == s[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            if i == len(d):\n",
    "                return d\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x:(-len(x),x))\n",
    "        # dictionary=dictionary[::-1]\n",
    "        for i in dictionary:\n",
    "            l=len(i)\n",
    "            j=0\n",
    "            for t in s:\n",
    "                if t==i[j]:\n",
    "                    j+=1\n",
    "                if j==l:\n",
    "                    return i\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ss = ''\n",
    "        zz = len(s)\n",
    "        for i in dictionary:\n",
    "            k0 = 0\n",
    "            k1 = 0\n",
    "            while k0 < len(i) and k1 < zz:\n",
    "                if i[k0] == s[k1]:\n",
    "                    k0 = k0 + 1\n",
    "                k1 = k1 + 1              \n",
    "            if k0 == len(i):\n",
    "                if k0 > len(ss):\n",
    "                    ss = i\n",
    "                elif k0 == len(ss):\n",
    "                    ss = min(ss, i)\n",
    "                else:\n",
    "                    pass\n",
    "        return ss\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = ''\n",
    "        for t in dictionary:\n",
    "            i, j = 0, 0\n",
    "            while j < len(s) and i < len(t):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        n1 = len(s)\n",
    "        res = ''\n",
    "        for t in dictionary:\n",
    "            n2 = len(t)\n",
    "            i, j = 0, 0\n",
    "            while i < n1 and j < n2:\n",
    "                if s[i] == t[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            if j == n2:\n",
    "                if n2 > len(res):\n",
    "                    res = t\n",
    "                elif n2 == len(res):\n",
    "                    res = min(res, t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        def find(s,target):\n",
    "            cur=0\n",
    "            for i in range(len(s)):\n",
    "                if cur<len(target) and s[i]==target[cur]:\n",
    "                    cur+=1\n",
    "            return cur>=len(target)\n",
    "        dictionary=[i for i in dictionary if find(s,i)]\n",
    "        if not dictionary:\n",
    "            return ''\n",
    "        e=max([len(i) for i in dictionary])\n",
    "        return min([i for i in dictionary if len(i)==e])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        sq = [x for x in s]\n",
    "        dic = {}\n",
    "        # path = []\n",
    "        def is_indic(dic_str):\n",
    "            if len(dic_str)>len(sq):\n",
    "                return False\n",
    "            l = r = 0\n",
    "            while l<len(dic_str) and r<len(sq):\n",
    "                if dic_str[l] not in sq:\n",
    "                    return False\n",
    "                if dic_str[l] !=sq[r]:\n",
    "                    r+=1\n",
    "                    l = l\n",
    "                elif dic_str[l] ==sq[r]:\n",
    "                    l+=1\n",
    "                    r+=1\n",
    "            if  l ==len(dic_str):\n",
    "                return True \n",
    "            return False\n",
    "        for j in dictionary:\n",
    "            if is_indic(j):\n",
    "                if len(j) in dic:\n",
    "                    dic[len(j)]  = dic[len(j)].union({j})\n",
    "                elif len(j) not in dic:\n",
    "                    dic[len(j)] = {j}\n",
    "                path.append(len(j))\n",
    "        if not dic:\n",
    "            return ''\n",
    "        ma = max(dic)\n",
    "        res = list(dic[ma])\n",
    "        res.sort()\n",
    "        if res:\n",
    "            return res[0]\n",
    "        else:\n",
    "            return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        real_s=s\n",
    "        s=dict()\n",
    "        for i,char in enumerate(real_s):\n",
    "            if char not in s:\n",
    "                s[char]=[]\n",
    "            s[char].append(i)\n",
    "        for key in s:\n",
    "            s[key].sort()\n",
    "        ret=[]\n",
    "        maxlen=0\n",
    "        for item in dictionary:\n",
    "            left=-1\n",
    "            judge=1\n",
    "            for char in item:\n",
    "                if char in s:\n",
    "                    index=bisect.bisect_left(s[char],left)\n",
    "                    if index==len(s[char]):\n",
    "                        judge=0\n",
    "                        break\n",
    "                    if s[char][index]!=left:\n",
    "                        left=s[char][index]\n",
    "                    else:\n",
    "                        if index+1>=len(s[char]):\n",
    "                            judge=0\n",
    "                            break\n",
    "                        left=s[char][index+1]\n",
    "                else:\n",
    "                    judge=0\n",
    "                    break\n",
    "            if judge==1:\n",
    "                maxlen=max(maxlen,len(item))\n",
    "                ret.append(item)\n",
    "        x=[]\n",
    "        for item in ret:\n",
    "            if len(item)==maxlen:\n",
    "                x.append(item)\n",
    "        x.sort()\n",
    "        if len(x)==0:\n",
    "            return \"\"\n",
    "        return x[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        n=len(s)\n",
    "        ans=\"\"\n",
    "        for word in dictionary:\n",
    "            i,j=0,0\n",
    "            while i<n and j<len(word):\n",
    "                if word[j]==s[i]:\n",
    "                    j+=1\n",
    "                i+=1\n",
    "            if j==len(word):\n",
    "                ans=word if len(word)==len(ans) and word<ans or len(word)>len(ans) else ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key = lambda x:(-len(x),x))\n",
    "        for d in dictionary:\n",
    "            i,j = 0,0\n",
    "            if len(d) > len(s):\n",
    "                continue\n",
    "            while i<len(d) and j<len(s):\n",
    "                if d[i] == s[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            if i == len(d):\n",
    "                return d\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ll = []\n",
    "        for k in dictionary:\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(k) and j < len(s):\n",
    "                if k[i] == s[j]:\n",
    "                    i+=1\n",
    "                j += 1\n",
    "            if i == len(k):\n",
    "                ll.append(k)\n",
    "        if not len(ll):\n",
    "            return \"\"\n",
    "        else:\n",
    "            return min(ll, key=lambda x: (-len(x),x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s, dictionary):\n",
    "        dictionary.sort()\n",
    "        dictionary.sort(key=lambda x: -len(x))\n",
    "        n = len(s)\n",
    "        for item in dictionary:\n",
    "            p0 = 0\n",
    "            count = 0\n",
    "            for key in item:\n",
    "                while p0 < n:\n",
    "                    if s[p0] != key:\n",
    "                        p0 += 1\n",
    "                    else:\n",
    "                        count += 1\n",
    "                        p0 += 1\n",
    "                        break\n",
    "            if count == len(item):\n",
    "                return item\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        \"\"\"\n",
    "        双指针\n",
    "        \"\"\"\n",
    "        rs = \"\"\n",
    "        for word in dictionary:\n",
    "            i,j = 0,0 #i指向s j指向word\n",
    "            while i<len(s):\n",
    "                if s[i]==word[j]:  \n",
    "                    j += 1\n",
    "                    if j==len(word):\n",
    "                        if not rs or len(rs) < len(word) or (len(word) == len(rs) and word < rs):\n",
    "                            rs = word\n",
    "                        break\n",
    "                i += 1\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ss = ''\n",
    "        zz = len(s)\n",
    "        for i in dictionary:\n",
    "            k0 = 0\n",
    "            k1 = 0\n",
    "            while k0 < len(i) and k1 < zz:\n",
    "                if i[k0] == s[k1]:\n",
    "                    k0 = k0 + 1\n",
    "                k1 = k1 + 1              \n",
    "            if k0 == len(i):\n",
    "                if k0 > len(ss):\n",
    "                    ss = i\n",
    "                elif k0 == len(ss):\n",
    "                    ss = min(ss, i)\n",
    "                else:\n",
    "                    pass\n",
    "        return ss\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x: (-len(x), x))\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                return t\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        def isSubStr(word):\n",
    "            nonlocal s\n",
    "            if len(word) > len(s):\n",
    "                return False\n",
    "            s_idx = w_idx = 0\n",
    "            while s_idx < len(s) and w_idx < len(word):\n",
    "                if s[s_idx] == word[w_idx]:\n",
    "                    w_idx += 1\n",
    "                s_idx +=1\n",
    "            return w_idx == len(word)\n",
    "\n",
    "\n",
    "        longest_word = \"\"\n",
    "        for word in dictionary:\n",
    "            if isSubStr(word) and (len(word) > len(longest_word) or (len(word)==len(longest_word) and word < longest_word)):\n",
    "                longest_word = word\n",
    "        return longest_word\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        l,m=len(dictionary),len(s)\n",
    "        res=0\n",
    "        for i in range(l):\n",
    "            starter=0\n",
    "            for j in range(m):\n",
    "                if starter<len(dictionary[i]) and s[j]==dictionary[i][starter]:\n",
    "                    starter+=1\n",
    "            #print(starter,i)\n",
    "            if starter==len(dictionary[i]):\n",
    "                \n",
    "                if res<len(dictionary[i]):\n",
    "                    local=dictionary[i]\n",
    "                    res=len(dictionary[i])\n",
    "                elif res==len(dictionary[i]) and dictionary[i]<local:\n",
    "                    local=dictionary[i]\n",
    "        if res==0:\n",
    "            return \"\"\n",
    "        else: \n",
    "            return local\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        sq = [x for x in s]\n",
    "        dic = {}\n",
    "        path = []\n",
    "        def is_indic(dic_str):\n",
    "            if len(dic_str)>len(sq):\n",
    "                return False\n",
    "            l = r = 0\n",
    "            while l<len(dic_str) and r<len(sq):\n",
    "                if dic_str[l] not in sq:\n",
    "                    return False\n",
    "                if dic_str[l] !=sq[r]:\n",
    "                    r+=1\n",
    "                    l = l\n",
    "                elif dic_str[l] ==sq[r]:\n",
    "                    l+=1\n",
    "                    r+=1\n",
    "            if  l ==len(dic_str):\n",
    "                return True \n",
    "            return False\n",
    "        for j in dictionary:\n",
    "            if is_indic(j):\n",
    "                if len(j) in dic:\n",
    "                    dic[len(j)]  = dic[len(j)].union({j})\n",
    "                elif len(j) not in dic:\n",
    "                    dic[len(j)] = {j}\n",
    "                path.append(len(j))\n",
    "        if not path:\n",
    "            return ''\n",
    "        ma = max(path)\n",
    "        res = list(dic[ma])\n",
    "        res.sort()\n",
    "        if res:\n",
    "            return res[0]\n",
    "        else:\n",
    "            return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ans = []\n",
    "        for i in dictionary:\n",
    "            temp, flag = 0, 0\n",
    "            for c in i:\n",
    "                if s.find(c, flag) != -1:\n",
    "                    temp += 1\n",
    "                    flag = s.index(c, flag) + 1\n",
    "            if temp == len(i):\n",
    "                ans.append(i)\n",
    "        if len(ans) == 0:\n",
    "            return ''\n",
    "        ans.sort(key=lambda x: len(x), reverse=True)\n",
    "        length = len(ans[0])\n",
    "        res = list(filter(lambda x: len(x) == length, ans))\n",
    "        res.sort()\n",
    "        return res[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for word in dictionary:\n",
    "            m = len(word)\n",
    "            if m < len(res):\n",
    "                continue\n",
    "            p, q = 0, 0\n",
    "            while p < len(s) and q < m:\n",
    "                if s[p] == word[q]:\n",
    "                    q += 1\n",
    "                p += 1\n",
    "            if q >= m:\n",
    "                if len(res) < m or word < res:\n",
    "                    res = word\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ll = []\n",
    "        for k in dictionary:\n",
    "            m = 0\n",
    "            i = 0\n",
    "            while m < len(k) and i < len(s):\n",
    "                if k[m] == s[i]:\n",
    "                    m += 1\n",
    "                i+=1\n",
    "            if m==len(k):\n",
    "                ll.append(k)\n",
    "        if not ll:\n",
    "            return ''\n",
    "        else:\n",
    "            return min(ll, key=lambda x: (-len(x), x)) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s, dictionary) -> str:\n",
    "        def isSubsequence(s, t):\n",
    "            n = len(s)\n",
    "            m = len(t)\n",
    "            if m > n:\n",
    "                return False\n",
    "            i = 0\n",
    "            for ch in t:\n",
    "                while i < n and s[i] != ch:\n",
    "                    i += 1\n",
    "                if i >= n:\n",
    "                    return False\n",
    "                i += 1\n",
    "            return True\n",
    "        dictionary.sort(key = lambda x: (-len(x), x))\n",
    "        for word in dictionary:\n",
    "            if isSubsequence(s, word):\n",
    "                return word \n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        sorted_d = sorted(dictionary, key = lambda x:[-len(x),x])\n",
    "\n",
    "        for i in sorted_d:\n",
    "            x = 0\n",
    "            y = 0\n",
    "            while y<len(s):\n",
    "                if s[y] == i[x]:\n",
    "                    x+=1\n",
    "                \n",
    "                if x == len(i):\n",
    "                    return i\n",
    "                \n",
    "\n",
    "                y+=1\n",
    "        \n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x: (-len(x), x))\n",
    "        for word in dictionary:\n",
    "            idx = 0\n",
    "            for ch in word:\n",
    "                idx = s.find(ch, idx) + 1\n",
    "                if not idx:\n",
    "                    break\n",
    "            else:\n",
    "                return word\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ans = []\n",
    "        for tmp in dictionary:\n",
    "            n = len(s)\n",
    "            m = len(tmp)\n",
    "            p = 0 # 指向s\n",
    "            q = 0 # 指向tmp\n",
    "            while p < n and q < m:\n",
    "                if s[p] == tmp[q]:\n",
    "                    q += 1\n",
    "                p += 1\n",
    "            if q == m:\n",
    "                ans.append(tmp)\n",
    "        ans.sort(key=lambda x:(-len(x),x))\n",
    "        # print(ans)\n",
    "        return ans[0] if len(ans) > 0 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str])->str:\n",
    "        #判断d是否是s的子序列\n",
    "        def isSub(s: str, d:str):\n",
    "            i = 0\n",
    "            for j in range(len(s)):\n",
    "                if d[i] == s[j]:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    continue\n",
    "                if i == len(d):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        res = []\n",
    "        for d in dictionary:\n",
    "            if isSub(s, d):\n",
    "                res.append(d)\n",
    "        res.sort(key=lambda x:(-len(x), x))\n",
    "        return res[0] if len(res)>0 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key = lambda x : (-len(x),x))\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                return t\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        # length = 0\n",
    "        # result = ''\n",
    "\n",
    "        # def if_contain(s, d):\n",
    "        #     i = j = 0\n",
    "        #     re = ''\n",
    "        #     while i < len(s) and j < len(d):\n",
    "        #         if s[i] == d[j]:\n",
    "        #             re += s[i]\n",
    "        #             i += 1\n",
    "        #             j += 1\n",
    "        #         else:\n",
    "        #             i += 1\n",
    "        #     if re == d:\n",
    "        #         return True\n",
    "\n",
    "\n",
    "        # for i in dictionary:\n",
    "        #     if if_contain(s, i):\n",
    "        #         if len(i) > length:\n",
    "        #             length = len(i)\n",
    "        #             result = i\n",
    "        #         elif len(i) == length:\n",
    "        #             result = min(result, i)\n",
    "        # return result\n",
    "\n",
    "        re = ''\n",
    "        for word in dictionary:\n",
    "            i = j = 0\n",
    "            tmp = ''\n",
    "            while i < len(s) and j < len(word):\n",
    "                if s[i] == word[j]:\n",
    "                    tmp += s[i]\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "                if tmp == word:\n",
    "                    if len(tmp) > len(re):\n",
    "                        re = tmp\n",
    "                    if len(tmp) == len(re):\n",
    "                        re = min(re, tmp)\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        sq = [x for x in s]\n",
    "        dic = {}\n",
    "        def is_indic(dic_str):\n",
    "            if len(dic_str)>len(sq):\n",
    "                return False\n",
    "            l = r = 0\n",
    "            while l<len(dic_str) and r<len(sq):\n",
    "                if dic_str[l] not in sq:\n",
    "                    return False\n",
    "                if dic_str[l] !=sq[r]:\n",
    "                    r+=1\n",
    "                    l = l\n",
    "                elif dic_str[l] ==sq[r]:\n",
    "                    l+=1\n",
    "                    r+=1\n",
    "            if  l ==len(dic_str):\n",
    "                return True \n",
    "            return False\n",
    "        for j in dictionary:\n",
    "            if is_indic(j):\n",
    "                if len(j) in dic:\n",
    "                    dic[len(j)]  = dic[len(j)].union({j})\n",
    "                elif len(j) not in dic:\n",
    "                    dic[len(j)] = {j}\n",
    "        if not dic:\n",
    "            return ''\n",
    "        ma = max(dic)\n",
    "        res = list(dic[ma])\n",
    "        res.sort()\n",
    "        \n",
    "        return res[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        res = \"\"\n",
    "        for word in dictionary:\n",
    "\n",
    "\n",
    "            i, j = 0, 0\n",
    "\n",
    "            while i < len(s) and j < len(word):\n",
    "\n",
    "                if s[i] == word[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            \n",
    "            if j == len(word):\n",
    "                if len(word) > len(res) or (len(word) == len(res) and word < res):\n",
    "                    res = word\n",
    "\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        # 对dictionary进行排序：长度越长、字母序越小\n",
    "        dictionary.sort(key=lambda x: [-len(x), x])\n",
    "        s_len = len(s)\n",
    "        for ceil in dictionary:\n",
    "            ceil_len = len(ceil)\n",
    "            if ceil_len > s_len:\n",
    "                continue\n",
    "            i = j = 0\n",
    "            while i < ceil_len and j < s_len:\n",
    "                # 双指针，但i固定的时候，遍历j直到找到跟i相等的值\n",
    "                if ceil[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == ceil_len:\n",
    "                return ceil\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = ''\n",
    "        for word in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(word) and j < len(s):\n",
    "                if word[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(word):\n",
    "                if len(word) > len(res) or (len(word) == len(res) and word < res):\n",
    "                    res = word\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x:(-len(x),x))\n",
    "        for i in range(len(dictionary)):\n",
    "            p_s, p_d = 0, 0\n",
    "            while p_s < len(s):\n",
    "                if dictionary[i][p_d] == s[p_s]:\n",
    "                    p_d += 1\n",
    "                    if p_d == len(dictionary[i]):\n",
    "                        return dictionary[i]\n",
    "                p_s += 1\n",
    "        return \"\"\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        n=len(s)\n",
    "        ans=\"\"\n",
    "        dictionary.sort(key=lambda x:(-len(x),x))\n",
    "        for word in dictionary:\n",
    "            i,j=0,0\n",
    "            while i<n and j<len(word):\n",
    "                if word[j]==s[i]:\n",
    "                    j+=1\n",
    "                i+=1\n",
    "            if j==len(word):\n",
    "                ans=word\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode: # has children and endOfWord\n",
    "    def __init__(self):\n",
    "        self.children = {} # can be 26 for English letters\n",
    "        self.endOfWord = False # check if word ends with a letter\n",
    "\n",
    "class Trie: # a tree like data structure to solve prefix problems in string\n",
    "    def __init__(self): # init the node\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None: # insert a word inside a Trie\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                cur.children[c] = TrieNode()\n",
    "            cur = cur.children[c]\n",
    "        cur.endOfWord = True\n",
    "\n",
    "    def search(self, word: str) -> bool: # check if a word inside trie\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                return False\n",
    "            cur = cur.children[c]\n",
    "            if cur.endOfWord == False:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        # t = Trie()\n",
    "        # for word in words:\n",
    "        #     t.insert(word)\n",
    "\n",
    "        # res = []\n",
    "        # for w in words:\n",
    "        #     if t.search(w):\n",
    "        #         res.append(w)\n",
    "        # if not res:\n",
    "        #     return ''\n",
    "        # res.sort(key = lambda x: (-len(x), x))\n",
    "        # return res[0]\n",
    "        res = \"\"\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "      dictionary.sort(key=lambda a:(-len(a),a))\n",
    "      ret=\"\"\n",
    "      for ss in dictionary:\n",
    "        if self.isSubSequence(s,ss):\n",
    "          return ss\n",
    "      return ret\n",
    "\n",
    "    def isSubSequence(self, s:str, ss:str)->bool:\n",
    "      # return if ss is a subsequence of s \n",
    "      i,j=0,0\n",
    "      m,n=len(s),len(ss)\n",
    "      while i<m and j<n:\n",
    "        if s[i]==ss[j]:\n",
    "          i+=1\n",
    "          j+=1\n",
    "        else:\n",
    "          i+=1\n",
    "      return j==n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x: (-len(x), x))\n",
    "        for x in dictionary:\n",
    "            if len(x) > len(s):\n",
    "                continue\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(s) and j < len(x):\n",
    "                if s[i] == x[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            if j == len(x):\n",
    "                return x\n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for t in dictionary:\n",
    "            i , j = 0 , 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        dp = [[-1] * 26 for _ in range(n+1)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(26):\n",
    "                if s[i] != chr(ord('a') + j):\n",
    "                    dp[i][j] = dp[i+1][j]\n",
    "                else:\n",
    "                    dp[i][j] = i\n",
    "        \n",
    "        ans = []\n",
    "        for string in dictionary:\n",
    "            i = 0\n",
    "            flag = True\n",
    "            for j in string:\n",
    "                i = dp[i][ord(j) - ord('a')]\n",
    "                if i == -1:\n",
    "                    flag = False\n",
    "                    break\n",
    "                i += 1\n",
    "            if flag:\n",
    "                ans.append(string)\n",
    "        \n",
    "        if not ans:\n",
    "            return ''\n",
    "        ans.sort()\n",
    "        maxlen = 0\n",
    "        for string in ans:\n",
    "            if len(string) > maxlen:\n",
    "                res = string\n",
    "                maxlen = len(string)\n",
    "        \n",
    "        return res \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        def can_derive(s1, s2):\n",
    "            if len(s1) <= len(s2):\n",
    "                return s1 == s2\n",
    "            char1, char2 = 0, 0\n",
    "            while char1 < len(s1) and char2 < len(s2):\n",
    "                if s1[char1] == s2[char2]:\n",
    "                    char2 += 1\n",
    "                char1 += 1\n",
    "            return char2 >= len(s2)\n",
    "        \n",
    "        for word in sorted(dictionary, key=lambda x: (-len(x), x)):\n",
    "            if can_derive(s, word):\n",
    "                return word\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for word in dictionary:\n",
    "            if len(word) < len(res):\n",
    "                continue\n",
    "            p, q = 0, 0\n",
    "            while p < len(s) and q < len(word):\n",
    "                if s[p] == word[q]:\n",
    "                    q += 1\n",
    "                p += 1\n",
    "            if q >= len(word):\n",
    "                if len(res) < len(word) or word < res:\n",
    "                    res = word\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        def helper(ds):\n",
    "            if len(ds) > len(s): return False\n",
    "\n",
    "            i, j = 0, 0\n",
    "            while i < len(ds) and j < len(s):\n",
    "                if ds[i] == s[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            # print(ds, i)\n",
    "            return i == len(ds)\n",
    "        \n",
    "        res = [i for i in dictionary if helper(i)]\n",
    "        res.sort(key=lambda x: (-len(x), x))\n",
    "        return res[0] if res else ''\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        #先把dict里面的元素按长度降序，字母升序排序\n",
    "        dictionary.sort(key = lambda elem: (-len(elem),elem)) #nlogn\n",
    "\n",
    "        #O(len(dict)*len(word)*len(s)) 经典贪心\n",
    "        for word in dictionary: \n",
    "            start_idx = 0\n",
    "            for letter in word:\n",
    "                #逐个字母匹配并记录匹配index\n",
    "                start_idx = s.find(letter,start_idx) + 1 \n",
    "                #匹配失败则跳出循环 进入下一个word\n",
    "                if not start_idx:\n",
    "                    break\n",
    "            if start_idx:#start_idx不为0 则整个word匹配成功 return\n",
    "                return word \n",
    "        return ''\n",
    "        \n",
    "        # O(len(dict)*len(s))\n",
    "        # for word in dictionary:\n",
    "        #     idx = 0\n",
    "        #     for c in s:\n",
    "        #         if idx < len(word) and c == word[idx]:\n",
    "        #             idx += 1\n",
    "        #     if idx == len(word):\n",
    "        #         return word\n",
    "        # return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                if len(t) > len(res) or (len(t) == len(res) and t < res):\n",
    "                    res = t\n",
    "        return res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        \n",
    "        #判断s是否为t的子序列\n",
    "        def isSub(s: str, t: str):\n",
    "            if not s:\n",
    "                return True\n",
    "            i = 0\n",
    "            for j in t:\n",
    "                if s[i] == j:\n",
    "                    i += 1\n",
    "                if len(s) == i:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        res = []\n",
    "        for d in dictionary:\n",
    "            if isSub(d, s):\n",
    "                res.append(d)\n",
    "        res.sort(key=lambda x:(-len(x), x))  #根据长度降序，根据字母顺序升序\n",
    "        return res[0] if res else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        m = len(s)\n",
    "        dictionary.sort(key=lambda x:-len(x))\n",
    "        res = \"\"\n",
    "\n",
    "        for i in range(len(dictionary)):\n",
    "            n = len(dictionary[i])\n",
    "            if n<len(res):\n",
    "                break\n",
    "            else:\n",
    "                j,k = 0,0 \n",
    "                while 0<=j<m and 0<=k<n:\n",
    "                    if s[j] == dictionary[i][k]:\n",
    "                        k += 1\n",
    "                    j += 1\n",
    "                if k==n:\n",
    "                    if res:\n",
    "                        j,k = 0,0\n",
    "                        while 0<=j<n and 0<=k<n and res[j] == dictionary[i][k]:\n",
    "                            j += 1\n",
    "                            k += 1\n",
    "                        \n",
    "                        if j<n and ord(res[j])>ord(dictionary[i][k]):\n",
    "                            res = dictionary[i]\n",
    "                    else:\n",
    "                        res = dictionary[i]\n",
    "                        \n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        s_c=Counter(s)\n",
    "        dictionary.sort(key=lambda x :[-len(x),x])\n",
    "        n=len(s)\n",
    "        for d in dictionary:\n",
    "            m=len(d)\n",
    "            i,j=0,0\n",
    "            while i<n and j<m:\n",
    "                if s[i]==d[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "            if j==m:\n",
    "                return d\n",
    "            \n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x:[-len(x),x])\n",
    "        for sub in dictionary:\n",
    "            ps, pd = 0, 0\n",
    "            while ps<len(s) and pd<len(sub):\n",
    "                if s[ps]==sub[pd]:\n",
    "                    ps+=1\n",
    "                    pd+=1\n",
    "                else:\n",
    "                    ps+=1\n",
    "            if pd==len(sub):\n",
    "                return sub\n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        # # 自定义排序函数\n",
    "        # def sort_func(item):\n",
    "        #     return (-len(item), item)\n",
    "        dictionary.sort(key = lambda x : (-len(x), x))\n",
    "\n",
    "        n_s = len(s)\n",
    "        for c in dictionary:\n",
    "            n_c = len(c)\n",
    "            i, j = 0, 0\n",
    "            while i < n_s and j < n_c:\n",
    "                if s[i] == c[j]:\n",
    "                    j += 1\n",
    "                \n",
    "                i += 1\n",
    "\n",
    "            if j == n_c:\n",
    "                return c\n",
    "        \n",
    "        return \"\"\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x:(-len(x), x))\n",
    "        # print(dictionary)\n",
    "\n",
    "        s_list = [[None for _ in range(26)] for _ in s]\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(26):\n",
    "                if ord(s[i]) == j+ord(\"a\"):\n",
    "                    s_list[i][j] = i\n",
    "                else:\n",
    "                    if (i<len(s)-1):\n",
    "                        s_list[i][j] = s_list[i+1][j]\n",
    "\n",
    "        # print(s_list)\n",
    "        for cur_word in dictionary:\n",
    "            s_index = 0\n",
    "            w_index = 0\n",
    "            while s_index<len(s):\n",
    "                # print(s_index, w_index, s_list[s_index][ord(cur_word[w_index])-ord(\"a\")])\n",
    "                if s_list[s_index][ord(cur_word[w_index])-ord(\"a\")] is None:\n",
    "                    break\n",
    "                else:\n",
    "                    s_index = s_list[s_index][ord(cur_word[w_index])-ord(\"a\")]+1\n",
    "                    w_index += 1\n",
    "                    if w_index==len(cur_word):\n",
    "                        return cur_word\n",
    "        return \"\"\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key = lambda x:(-len(x), x))\n",
    "        def check(word, s):\n",
    "            if len(word) > len(s):\n",
    "                return False\n",
    "            l = 0\n",
    "            for c in s:\n",
    "                if c == word[l]:\n",
    "                    l += 1\n",
    "                if l == len(word):\n",
    "                    return True\n",
    "            return False\n",
    "        for word in dictionary:\n",
    "            if check(word, s):\n",
    "                return word\n",
    "        return ''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        ## 用好python内置函数sort()、find(),比双指针效率更高\n",
    "        ## 可以用元组表示多关键字排序，第一关键字是长度降序，第二关键字是字符串本身字典序\n",
    "        dictionary.sort(key = lambda x: (-len(x), x))\n",
    "\n",
    "        for word in dictionary:\n",
    "            index = 0\n",
    "            for ch in word:\n",
    "                index = s.find(ch, index) + 1  # find输出-1:False\n",
    "                if not index:\n",
    "                    break\n",
    "            else:       # 这里用else语句保证break之后不会执行，正常循环结束会执行\n",
    "                return word\n",
    "\n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        #先把dict里面的元素按长度降序，字母升序排序\n",
    "        dictionary.sort(key = lambda elem: (-len(elem),elem)) #nlogn\n",
    "\n",
    "        for word in dictionary: # n*len(word)*len(s)\n",
    "            start_idx = 0\n",
    "            for letter in word:\n",
    "                start_idx = s.find(letter,start_idx) + 1\n",
    "                if not start_idx:#匹配失败 跳过\n",
    "                    break\n",
    "            else:\n",
    "                return word \n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda  x:(-len(x),x))\n",
    "        for  x in dictionary:\n",
    "            i = j=0\n",
    "            while i<len(x) and j <len(s):\n",
    "                if x[i]==s[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    j+=1\n",
    "            if i==len(x):\n",
    "                return  x\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        #判断dic里的字符串是否是s的子序列，双指针\n",
    "        dictionary.sort(key = lambda x: (-len(x), x))\n",
    "        \n",
    "        for t in dictionary:\n",
    "            i, j = 0, 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i+=1\n",
    "                j += 1\n",
    "\n",
    "            if i == len(t):\n",
    "                return t\n",
    "        return ''\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        dictionary = sorted(dictionary, key=lambda x: (-len(x), x))\n",
    "        ans = []\n",
    "        for e in dictionary:\n",
    "            i, j = 0, 0\n",
    "            while i < n and j < len(e):\n",
    "                if s[i] == e[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            if j == len(e):\n",
    "                ans.append(e)\n",
    "            \n",
    "        if not ans:\n",
    "            return ''\n",
    "        \n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s, dictionary):\n",
    "        dictionary.sort(key=lambda x: (-len(x), x))\n",
    "        n = len(s)\n",
    "        for item in dictionary:\n",
    "            p0 = 0\n",
    "            count = 0\n",
    "            for key in item:\n",
    "                while p0 < n:\n",
    "                    if s[p0] != key:\n",
    "                        p0 += 1\n",
    "                    else:\n",
    "                        count += 1\n",
    "                        p0 += 1\n",
    "                        break\n",
    "            if count == len(item):\n",
    "                return item\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x: (-len(x), x))\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(t) and j < len(s):\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(t):\n",
    "                return t\n",
    "        return \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestWord(self, s: str, dictionary: List[str]) -> str:\n",
    "        dictionary.sort(key=lambda x: (-len(x), x))\n",
    "        for t in dictionary:\n",
    "            i = j = 0\n",
    "            while i < len(s) and j < len(t):\n",
    "                if s[i] == t[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "\n",
    "            if j == len(t):\n",
    "                return t\n",
    "        \n",
    "        return \"\""
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
